//--------------------------------------------------------
/* kdTree.h
 * An implementation of kdTree for three dimensions.
 * Here again, the dimension problem should be payed 
 * attention to: for 3 dimensional data, the kdtree
 * works well, but for 2 dimensional data, the last 
 * coordinate of the data(that is z) is supposed to
 * be 0 to allow the algrithom to work well.

                                    LuXinlai - Apr 2008
--------------------------------------------------------*/

#ifndef KDTREE_H
#define KDTREE_H

//#define DEBUG
#define TYPE double

#include <iostream>
#include <cstdlib>
using namespace std;

// When I upgraded the system, something was wrong about the
// system libraries, and it's needed to add the "extern "C""
// to declare the exit function. And it seems that the function 
// has to be apended by "throw()". 
//extern "C"
//{
//	void exit(int);
//}

// This is the node in the tree
//********************
typedef struct kdNode
//********************
{
	TYPE pos[3];             //node coordinate    
	short plane;             //the spliting plane of a node in the tree
	int   id;                //the ID of a node which is from the data file of UCD format
}kdNode;

/* This is used only to locate
 * the nearest nodes in the tree
*/
//************************
class nNearestNodes
//************************
{	
public:
	nNearestNodes(const int maximum)
	{
		max = maximum;
		found = got_Heap = 0;

		dist2 = new double[max + 1];
		index = new const kdNode*[max + 1];
	}
	~nNearestNodes()
	{
		delete []dist2;
		delete []index;
	}
	void setDistError(double error)
	{
		dist2[0] = error;
	}
	void setSearchPnt(const double x, const double y, const double z)
	{
		pos[0] = x;
		pos[1] = y;
		pos[2] = z;
	}

	int max;                 //the number of nearest nodes
	int found;               //the number of nNN currently found in the process of search
	int got_Heap;            //whether to build a heap for the nNN found
	double pos[3];             //the coordinates of a specified point
	double *dist2;            //dist[0],dist[...]
	const kdNode **index;    //index[1,...]	
};

/* This is the kdTree class
 */
//***********
class kdTree
//***********
{
public:
	kdTree(){}
	kdTree(const size_t totalNodes);
	void set(const size_t totalNodes);
	~kdTree();

	void store(
		const TYPE xCoord,
		const TYPE yCoord,
		const TYPE zCoord
	);
	inline void store(
		const TYPE xCoord,
		const TYPE yCoord,
		const TYPE zCoord,
		const int   pId
		);
	inline void store(
		const TYPE coords[3],
		const int pId
		);

	void treeBalance();

	void locateNodes(
		nNearestNodes *const nNN,
		const int index
		)const;
	
	kdNode *kdNodes;

	int maxNumOfNodes;
#ifndef DEBUG
private:
#endif
	void balancePartition(
		kdNode **pBalanced,
		kdNode **pOriginal,
		const int index,
		const int start,
		const int end
		);

	void medianPartition(
		kdNode **pOrig,
		const int start,
		const int end,
		const int median,
		const int axis
		);

//	kdNode *kdNodes;

	size_t pntId;
	int storedKDNodes;
	int halfStoredKDNodes;
	//int maxNumOfNodes;

	double boundrayMin[3];
	double boundrayMax[3];
};

#endif

